Skip to main content

Reverse a Linked List

Problem​

Given a linked list of N nodes, the task is to reverse this list.

Examples​

Example 1:

Input:
LinkedList: 1->2->3->4->5->6
Output:
6 5 4 3 2 1

Explanation:
After reversing the list, elements are 6->5->4->3->2->1.

Example 2:

Input:
LinkedList: 2->7->8->9->10
Output:
10 9 8 7 2

Explanation:
After reversing the list, elements are 10->9->8->7->2.

Your Task​

The task is to complete the function reverseList() with head reference as the only argument and should return the new head after reversing the list.

Expected Time Complexity: O(N)O(N) Expected Auxiliary Space: O(1)O(1)

Constraints​

  • 1≤N≤1041 ≤ N ≤ 10^4

Solution​

Approach​

To reverse a linked list, we can follow these steps:

  1. Initialize three pointers: prev (previous node), curr (current node), and nextNode (next node).
  2. Start with prev = None and curr = head, where head is the head of the original linked list.
  3. Traverse the linked list:
    • Store nextNode as curr.next.
    • Reverse the link by pointing curr.next to prev.
    • Move prev to curr and curr to nextNode.
  4. After traversing, update the new head to prev.
  5. Return the new head.

Implementation​

class Solution:
# Function to reverse a linked list.
def reverseList(self, head):
prev = None
curr = head

while curr:
nextNode = curr.next
curr.next = prev
prev = curr
curr = nextNode

head = prev
return head

Complexity Analysis​

  • Time Complexity: O(N)O(N), where N is the number of nodes in the linked list. We traverse the entire list once.
  • Space Complexity: O(1)O(1), as we only use a constant amount of extra space for pointers.

References​